{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Two Sum IV - Input is a BST"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #breadth-first-search #binary-search-tree #hash-table #two-pointers #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #广度优先搜索 #二叉搜索树 #哈希表 #双指针 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findTarget"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #两数之和 IV - 输入二叉搜索树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个二叉搜索树 <code>root</code> 和一个目标结果 <code>k</code>，如果二叉搜索树中存在两个元素且它们的和等于给定的目标结果，则返回 <code>true</code>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/09/21/sum_tree_1.jpg\" style=\"height: 229px; width: 400px;\" />\n",
    "<pre>\n",
    "<strong>输入:</strong> root = [5,3,6,2,4,null,7], k = 9\n",
    "<strong>输出:</strong> true\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/09/21/sum_tree_2.jpg\" style=\"height: 229px; width: 400px;\" />\n",
    "<pre>\n",
    "<strong>输入:</strong> root = [5,3,6,2,4,null,7], k = 28\n",
    "<strong>输出:</strong> false\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>二叉树的节点个数的范围是&nbsp;&nbsp;<code>[1, 10<sup>4</sup>]</code>.</li>\n",
    "\t<li><code>-10<sup>4</sup>&nbsp;&lt;= Node.val &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li>题目数据保证，输入的 <code>root</code> 是一棵 <strong>有效</strong> 的二叉搜索树</li>\n",
    "\t<li><code>-10<sup>5</sup>&nbsp;&lt;= k &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [two-sum-iv-input-is-a-bst](https://leetcode.cn/problems/two-sum-iv-input-is-a-bst/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [two-sum-iv-input-is-a-bst](https://leetcode.cn/problems/two-sum-iv-input-is-a-bst/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[5,3,6,2,4,null,7]\\n9', '[5,3,6,2,4,null,7]\\n28']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def findTarget(self, root: TreeNode, k: int) -> bool:\n",
    "        if root is None or (root.left is None and root.right is None): return False\n",
    "        queue = collections.deque([root])\n",
    "        val_list = []\n",
    "        while queue:\n",
    "            curr = queue.popleft()\n",
    "            if k - curr.val in val_list:\n",
    "                return True\n",
    "            val_list.append(curr.val)\n",
    "            if curr.left is not None:\n",
    "                queue.append(curr.left)\n",
    "            if curr.right is not None:\n",
    "                queue.append(curr.right)\n",
    "        return False\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTarget(self, root, k):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :type k: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if root==None:\n",
    "            return False\n",
    "        l=[]        \n",
    "        bfs=[root]\n",
    "        for i in bfs:\n",
    "            if i.val in l:\n",
    "                return True\n",
    "            l.append(k-i.val)\n",
    "            if i.left:\n",
    "                bfs.append(i.left)\n",
    "            if i.right:\n",
    "                bfs.append(i.right)\n",
    "        return False\n",
    "#         def findtree(root,k,l):\n",
    "#             if root==None:\n",
    "#                 return False\n",
    "#             if root.val in l:\n",
    "#                 return True\n",
    "#             l.append(k-root.val)\n",
    "#             return findtree(root.left,k,l) or findtree(root.right,k,l)\n",
    "        \n",
    "#         return findtree(root.left,k,l) or findtree(root.right,k,l)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTarget(self, root, k):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :type k: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        #利用 中序遍历得有序数组后，利用左右指针往中间夹\n",
    "        if not root:\n",
    "            return False\n",
    "        val=[]\n",
    "        def inorder(root):\n",
    "            if not root:\n",
    "                return \n",
    "            inorder(root.left)\n",
    "            val.append(root.val)\n",
    "            inorder(root.right)\n",
    "        \n",
    "        inorder(root)\n",
    "        \n",
    "        length=len(val)\n",
    "        \n",
    "        left=0\n",
    "        right=length-1\n",
    "        \n",
    "        while left<right:\n",
    "            sumval=val[left]+val[right]\n",
    "            if sumval==k:\n",
    "                return True\n",
    "            elif sumval<k:\n",
    "                left+=1\n",
    "            else:\n",
    "                right-=1\n",
    "        return False\n",
    "            \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTarget(self, root, k):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :type k: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        stk, s = [root], set()\n",
    "        while len(stk) > 0:\n",
    "            cur = stk.pop()\n",
    "            if cur:\n",
    "                if k - cur.val in s:\n",
    "                    return True\n",
    "                s.add(cur.val)\n",
    "                stk.append(cur.right)\n",
    "                stk.append(cur.left)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTarget(self, root, k):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :type k: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        res = set()\n",
    "        def inOrder(root):\n",
    "            if not root:\n",
    "                return False\n",
    "            if k - root.val in res:\n",
    "                return True\n",
    "            res.add(root.val)\n",
    "            return inOrder(root.left) or inOrder(root.right)\n",
    "        return inOrder(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def findTarget(self, root: 'TreeNode', k: 'int') -> 'bool':\n",
    "        self.d=defaultdict(int)\n",
    "        def over(root):\n",
    "            if root:\n",
    "                self.d[root.val]+=1\n",
    "                over(root.left)\n",
    "                over(root.right)\n",
    "        over(root)\n",
    "        # print(self.d)\n",
    "        keys=self.d.keys()\n",
    "        for key in keys:\n",
    "            if k-key !=key:\n",
    "                if k-key in keys:\n",
    "                    return True\n",
    "            else:\n",
    "                if self.d[key] >1:\n",
    "                    return True\n",
    "        return False\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def findTarget(self, root: TreeNode, k: int) -> bool:\n",
    "        def help(root):\n",
    "            if not root:\n",
    "                return []\n",
    "            s = []\n",
    "            s = s+help(root.left)\n",
    "            s.append(root.val)\n",
    "            s = s+help(root.right)\n",
    "            return s\n",
    "        a = help(root)\n",
    "        for i in a:\n",
    "            for j in a:\n",
    "                if i != j:\n",
    "                    if i+j == k:\n",
    "                        return True\n",
    "        return False\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTarget(self, root, k):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :type k: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if root==None:\n",
    "            return False \n",
    "        else :\n",
    "            stack=[root]\n",
    "            dicts={}\n",
    "            while stack:\n",
    "                \n",
    "                node=stack.pop(0)\n",
    "                dicts[node.val]=k-node.val\n",
    "                if node.left:\n",
    "                    stack.append(node.left)\n",
    "                if node.right:\n",
    "                    stack.append(node.right)\n",
    "                \n",
    "            for key in dicts.keys():\n",
    "                if key in dicts.values() and dicts[key]!=key :\n",
    "                    return True\n",
    "                \n",
    "            return False\n",
    "                \n",
    "                    \n",
    "                    \n",
    "                \n",
    "                \n",
    "                            \n",
    "                    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTarget(self, root, k):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :type k: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if root == None:\n",
    "            return False\n",
    "        self.flag = False\n",
    "        tra_set = set()\n",
    "        def tra(root, k):\n",
    "            if root != None:\n",
    "                if root.val not in tra_set:\n",
    "                    tra_set.add(k - root.val)\n",
    "                else:\n",
    "                    self.flag = True\n",
    "            else:\n",
    "                return\n",
    "            tra(root.left, k)\n",
    "            tra(root.right, k)\n",
    "            \n",
    "        tra(root, k)\n",
    "        return self.flag\n",
    "                    \n",
    "                \n",
    "        \n",
    "        \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self, root):\n",
    "        if not root:\n",
    "            return \n",
    "        self.arr.append(root.val)\n",
    "        self.dfs(root.left)\n",
    "        self.dfs(root.right)\n",
    "        \n",
    "    def findTarget(self, root, k):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :type k: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        self.arr = []\n",
    "        self.dfs(root)\n",
    "        dic = collections.defaultdict(int)\n",
    "        for i in self.arr:\n",
    "            dic[i] += 1\n",
    "        s = set(self.arr)\n",
    "        for i in s:\n",
    "            s.remove(i)\n",
    "            if k-i in s:\n",
    "                return True\n",
    "            s.add(i)\n",
    "        return False\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def findTarget(self, root: TreeNode, k: int) -> bool:\n",
    "        if not root: return False\n",
    "        stack, pre = [(root, 0)], []\n",
    "        while stack:\n",
    "            node, visited = stack.pop()\n",
    "            if node:\n",
    "                if visited:\n",
    "                    if pre:\n",
    "                        if pre[0] + node.val > k: return False\n",
    "                        elif pre[-1] + node.val >= k:\n",
    "                            for i in pre:\n",
    "                                if node.val + i == k: return True                \n",
    "                    pre.append(node.val)\n",
    "                else:\n",
    "                    stack.append((node.right, 0))\n",
    "                    stack.append((node, 1))\n",
    "                    stack.append((node.left, 0))\n",
    "\n",
    "\n",
    "        # if not root: return False\n",
    "        # queue, res = collections.deque([root]), []\n",
    "        # while queue:\n",
    "        #     node = queue.popleft()\n",
    "        #     if node:                \n",
    "        #         for i in res:\n",
    "        #             if node.val + i == k:\n",
    "        #                 return True                \n",
    "        #         res.append(node.val)\n",
    "        #         queue.append(node.left)\n",
    "        #         queue.append(node.right)\n",
    "        # return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def findTarget(self, root: TreeNode, k: int) -> bool:\n",
    "        self.k = k\n",
    "        self.visited = set()\n",
    "        self.find = False\n",
    "        self.inOrder(root)\n",
    "        return self.find\n",
    "        \n",
    "    def inOrder(self, root):\n",
    "        if not root:\n",
    "            return\n",
    "        if self.find:\n",
    "            return\n",
    "        self.inOrder(root.left)\n",
    "        if self.k - root.val in self.visited:\n",
    "            self.find = True\n",
    "        self.visited.add(root.val)\n",
    "        self.inOrder(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def findTarget(self, root: TreeNode, k: int) -> bool:\n",
    "        def inorder(root):\n",
    "            if not root:\n",
    "                return []\n",
    "            return inorder(root.left)+[root.val]+inorder(root.right)\n",
    "        numbers = sorted(inorder(root))\n",
    "        n = len(numbers)\n",
    "           \n",
    "        i = 0\n",
    "        j = n-1\n",
    "        while i < j:\n",
    "            if numbers[i] + numbers[j] > k:\n",
    "                j -= 1\n",
    "            elif numbers[i] + numbers[j] < k:\n",
    "                i +=1\n",
    "            else:\n",
    "                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def findTarget(self, root, k) :\n",
    "        def inorder(root,ans_list):\n",
    "            if not root:\n",
    "                return ans_list\n",
    "            ans_list = inorder(root.left,ans_list)\n",
    "            ans_list.append(root.val)\n",
    "            ans_list = inorder(root.right,ans_list)\n",
    "            return ans_list\n",
    "        tree_list = inorder(root,[])\n",
    "        tree_dict = {}\n",
    "        for index,value in enumerate(tree_list):\n",
    "            if (tree_dict.get(k-value) is not None) :\n",
    "                return True\n",
    "            tree_dict[value] = index\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTarget(self, root: TreeNode, k: int) -> bool:\n",
    "        ele = []\n",
    "        queue = []\n",
    "        if root:\n",
    "            queue.append(root)\n",
    "        while queue:\n",
    "            n = len(queue)\n",
    "            for i in range(n):\n",
    "                node = queue.pop(0)\n",
    "                ele.append(node.val)\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "        ele.sort()\n",
    "        for i in range(len(ele)):\n",
    "            if i == len(ele)-1:\n",
    "                temp = ele[:i]\n",
    "            else:\n",
    "                temp = ele[:i]+ele[i+1:]\n",
    "            if k-ele[i] in temp:\n",
    "                return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTarget(self, root: TreeNode, k: int) -> bool:\n",
    "        # bfs\n",
    "        from queue import Queue\n",
    "        if not root:\n",
    "            return False\n",
    "        setc = set()\n",
    "        q = Queue()\n",
    "        q.put(root)\n",
    "        while not q.empty():\n",
    "            node = q.get()\n",
    "            if k - node.val in setc:\n",
    "                return True\n",
    "            else:\n",
    "                if node.left:\n",
    "                    q.put(node.left)\n",
    "                if node.right:\n",
    "                    q.put(node.right)\n",
    "            setc.add(node.val)\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTarget(self, root: TreeNode, k: int) -> bool:\n",
    "        # bfs\n",
    "        from queue import Queue\n",
    "        if not root:\n",
    "            return False\n",
    "        setc = set()\n",
    "        q = Queue()\n",
    "        q.put(root)\n",
    "        while not q.empty():\n",
    "            node = q.get()\n",
    "            if k - node.val in setc:\n",
    "                return True\n",
    "            else:\n",
    "                if node.left:\n",
    "                    q.put(node.left)\n",
    "                if node.right:\n",
    "                    q.put(node.right)\n",
    "            setc.add(node.val)\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTarget(self, root: TreeNode, k: int) -> bool:       \n",
    "\n",
    "        if not root:\n",
    "            return False\n",
    "        s = set()\n",
    "        queue = [root]\n",
    "        while queue:\n",
    "            node = queue.pop(0)\n",
    "            s.add(node.val)\n",
    "            if node.left:\n",
    "                queue.append(node.left)\n",
    "            if node.right:\n",
    "                queue.append(node.right)\n",
    "        for num in s:\n",
    "            if k - num in s and 2 * (k - num) != k:\n",
    "                return True\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTarget(self, root: TreeNode, k: int) -> bool:\n",
    "        self.hashmap = set()\n",
    "        self.k = k\n",
    "        res = self.dfs(root)\n",
    "        return res\n",
    "        \n",
    "    def dfs(self, root):\n",
    "        if not root:return False\n",
    "        if self.hashmap and self.k-root.val in self.hashmap:\n",
    "            return True\n",
    "        self.hashmap.add(root.val)\n",
    "        left = self.dfs(root.left)\n",
    "        if left:return True\n",
    "        right = self.dfs(root.right)\n",
    "        if right:return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTarget(self, root: TreeNode, k: int) -> bool:\n",
    "        stack=[]\n",
    "        vis=[]\n",
    "        cur=root\n",
    "        while stack or cur:\n",
    "            while cur:\n",
    "                stack.append(cur)\n",
    "                cur = cur.left\n",
    "            tmp = stack.pop()\n",
    "            vis.append(tmp.val)\n",
    "            cur = tmp.right\n",
    "        l,r=0,len(vis)-1\n",
    "        while l<r:\n",
    "            if vis[l]+vis[r]==k:\n",
    "                return True\n",
    "            elif vis[l]+vis[r]<k:\n",
    "                l+=1\n",
    "            elif vis[l]+vis[r]>k:\n",
    "                r-=1\n",
    "        return False\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right   \n",
    "class Solution:\n",
    "    #def __init__(self):\n",
    "        #self.s = set()\n",
    "\n",
    "    def findTarget(self, root: Optional[TreeNode], k: int) -> bool:\n",
    "        \"\"\"\n",
    "        if root is None:\n",
    "            return False\n",
    "        if k - root.val in self.s:\n",
    "            return True\n",
    "        self.s.add(root.val)\n",
    "        return self.findTarget(root.left, k) or self.findTarget(root.right, k)\n",
    "        \"\"\"\n",
    "        nums = []\n",
    "        st = []\n",
    "        p = root\n",
    "        while p is not None or st:\n",
    "            while p is not None:\n",
    "                st.append(p)\n",
    "                p = p.left\n",
    "            p = st.pop()\n",
    "            nums.append(p.val)\n",
    "            p = p.right\n",
    "        \n",
    "        n = len(nums)\n",
    "        i, j = 0, n-1\n",
    "        while i < j:\n",
    "            if nums[i] + nums[j] == k:\n",
    "                return True\n",
    "            elif nums[i] + nums[j] > k:\n",
    "                j -= 1\n",
    "            else:\n",
    "                i += 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTarget(self, root: Optional[TreeNode], k: int) -> bool:\n",
    "        stack = [root]\n",
    "        hasmap = dict()\n",
    "        while stack:\n",
    "            q = stack.pop()\n",
    "            num = q.val\n",
    "            if num not in hasmap:\n",
    "                hasmap[num] = num\n",
    "                if k-num in hasmap and hasmap[k-num]!=hasmap[num]:\n",
    "                    return True\n",
    "            if q.left:\n",
    "                stack.append(q.left)\n",
    "            if q.right:\n",
    "                stack.append(q.right)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTarget(self, root: Optional[TreeNode], k: int) -> bool:\n",
    "        WHITE, BLACK = False, True\n",
    "        stack, nums = [(WHITE, root)], []\n",
    "        while stack:\n",
    "            color, node = stack.pop()\n",
    "            if not node:\n",
    "                continue\n",
    "            if not color:\n",
    "                stack.append((WHITE, node.right))\n",
    "                stack.append((BLACK, node))\n",
    "                stack.append((WHITE, node.left))\n",
    "            else:\n",
    "                nums.append(node.val)\n",
    "        n = len(nums)\n",
    "        i, j = 0, n-1\n",
    "        while i < j:\n",
    "            if nums[i] + nums[j] == k:\n",
    "                return True\n",
    "            elif nums[i] + nums[j] < k:\n",
    "                i += 1\n",
    "            else:\n",
    "                j -= 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "from collections import deque\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findTarget(self, root: Optional[TreeNode], k: int) -> bool:\n",
    "        queue = deque([root])\n",
    "        while queue:\n",
    "            cur = queue.popleft()\n",
    "            first_val = cur.val\n",
    "            second_val = k - first_val\n",
    "            if second_val < first_val:\n",
    "                if self.findVal(root, second_val):\n",
    "                    return True\n",
    "            elif second_val > first_val:\n",
    "                if self.findVal(root, second_val):\n",
    "                    return True\n",
    "\n",
    "            if cur.left:\n",
    "                queue.append(cur.left)\n",
    "            if cur.right:\n",
    "                queue.append(cur.right)\n",
    "\n",
    "        return False\n",
    "\n",
    "    def findVal(self, root, val):\n",
    "        cur = root\n",
    "        while cur.val != val:\n",
    "            if val > cur.val:\n",
    "                cur = cur.right\n",
    "            else:\n",
    "                cur = cur.left\n",
    "\n",
    "            if not cur:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.s = []\n",
    "        self.d = {}\n",
    "    def findTarget(self, root: [TreeNode], k: int) -> bool:\n",
    "        self.dfs(root)\n",
    "        print(self.d)\n",
    "        for key in self.d.keys():\n",
    "            if k - key in self.d.keys() and k - key != key:\n",
    "                return True\n",
    "        return False\n",
    "    def dfs(self, root):\n",
    "        self.s.append(root)\n",
    "        while len(self.s) > 0:\n",
    "            current = self.s.pop()\n",
    "            if current.val in self.d.keys():\n",
    "                self.d[current.val] += 1\n",
    "            else:\n",
    "                self.d[current.val] = 1\n",
    "            if current.left is not None:\n",
    "                self.s.append(current.left)\n",
    "            if current.right is not None:\n",
    "                self.s.append(current.right)\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTarget(self, root: Optional[TreeNode], k: int) -> bool:\n",
    "        left, right = root, root\n",
    "        leftStk, rightStk = [left], [right]\n",
    "        while left.left:\n",
    "            left = left.left\n",
    "            leftStk.append(left)\n",
    "        while right.right:\n",
    "            right = right.right\n",
    "            rightStk.append(right)\n",
    "        while left != right:\n",
    "            sum = left.val + right.val\n",
    "            if sum == k:\n",
    "                return True\n",
    "            if sum < k:\n",
    "                left = leftStk.pop()\n",
    "                node = left.right\n",
    "                while node:\n",
    "                    leftStk.append(node)\n",
    "                    node = node.left\n",
    "            else:\n",
    "                right = rightStk.pop()\n",
    "                node = right.left\n",
    "                while node:\n",
    "                    rightStk.append(node)\n",
    "                    node = node.right\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTarget(self, root: Optional[TreeNode], k: int) -> bool:\n",
    "        left, right = root, root\n",
    "        leftStk, rightStk = [left], [right]\n",
    "        while left.left:\n",
    "            left = left.left\n",
    "            leftStk.append(left)\n",
    "        while right.right:\n",
    "            right = right.right\n",
    "            rightStk.append(right)\n",
    "        while left != right:\n",
    "            sum = left.val + right.val\n",
    "            if sum == k:\n",
    "                return True\n",
    "            if sum < k:\n",
    "                left = leftStk.pop()\n",
    "                node = left.right\n",
    "                while node:\n",
    "                    leftStk.append(node)\n",
    "                    node = node.left\n",
    "            else:\n",
    "                right = rightStk.pop()\n",
    "                node = right.left\n",
    "                while node:\n",
    "                    rightStk.append(node)\n",
    "                    node = node.right\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTarget(self, root: Optional[TreeNode], k: int) -> bool:\n",
    "        ss=set()\n",
    "        q=deque([root])\n",
    "        while q:\n",
    "            node=q.pop()\n",
    "            if k-node.val in ss:\n",
    "                return True\n",
    "            ss.add(node.val)\n",
    "            if node.left:\n",
    "                q.append(node.left)\n",
    "            if node.right:\n",
    "                q.append(node.right)\n",
    "        return False\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\n",
    "\n",
    "# 中序遍历将二叉搜索树转换为有序数组后 双指针查找即可\n",
    "class Solution0:\n",
    "    def findTarget(self, root: Optional[TreeNode], k: int) -> bool:\n",
    "        def travese(root: Optional[TreeNode]):\n",
    "            res = list()\n",
    "            if not root:\n",
    "                return res\n",
    "            res.extend(travese(root.left))\n",
    "            res.append(root.val)\n",
    "            res.extend(travese(root.right))\n",
    "            return res\n",
    "\n",
    "        arr = travese(root)\n",
    "        l, r = 0, len(arr) - 1\n",
    "        while l < r:\n",
    "            sum = arr[l] + arr[r]\n",
    "            if sum < k:\n",
    "                l += 1\n",
    "            elif sum > k:\n",
    "                r -= 1\n",
    "            else:\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "\n",
    "# 对于一个值为 x 的节点，我们检查哈希表中是否存在 k-x 即可。如果存在对应的元素，那么我们就可以在该树\n",
    "# 上找到两个节点的和为k，否则我们将 x 放入哈希表中\n",
    "# 深搜版本：\n",
    "class Solution1:\n",
    "    def __init__(self):\n",
    "        self.s = set()\n",
    "\n",
    "    def findTarget(self, root: Optional[TreeNode], k: int) -> bool:\n",
    "        if root is None:\n",
    "            return False\n",
    "        if k - root.val in self.s:\n",
    "            return True\n",
    "        self.s.add(root.val)\n",
    "        return self.findTarget(root.left, k) or self.findTarget(root.right, k)\n",
    "\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "\n",
    "# 广搜版本：\n",
    "class Solution:\n",
    "    def findTarget(self, root: Optional[TreeNode], k: int) -> bool:\n",
    "        s = set()\n",
    "        q = deque([root])\n",
    "        while q:\n",
    "            node = q.popleft()\n",
    "            if k - node.val in s:\n",
    "                return True\n",
    "            s.add(node.val)\n",
    "            if node.left is not None:\n",
    "                q.append(node.left)\n",
    "            if node.right is not None:\n",
    "                q.append(node.right)\n",
    "        return False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTarget(self, root: Optional[TreeNode], k: int) -> bool:\n",
    "        xs = set()\n",
    "        def find(root):\n",
    "            if root is None:\n",
    "                return False\n",
    "            if (k - root.val) in xs:\n",
    "                return True\n",
    "            xs.add(root.val)\n",
    "            return find(root.left) or find(root.right)\n",
    "\n",
    "        return find(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTarget(self, root: Optional[TreeNode], k: int) -> bool:\n",
    "        knownList = dict()\n",
    "        while root:\n",
    "            if root.left:\n",
    "                pre = root.left\n",
    "                while pre.right != None and pre.right != root:\n",
    "                    pre = pre.right\n",
    "                if not pre.right:\n",
    "                    pre.right = root\n",
    "                    if knownList.get(k - root.val, None) != None:\n",
    "                        return True\n",
    "                    knownList[root.val] = root.val\n",
    "                        \n",
    "                    root = root.left\n",
    "                else:\n",
    "                    root = root.right\n",
    "            else:\n",
    "                if knownList.get(k - root.val, None) != None:\n",
    "                    return True\n",
    "                knownList[root.val] = root.val\n",
    "                root = root.right\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\r\n",
    "# class TreeNode:\r\n",
    "#     def __init__(self, val=0, left=None, right=None):\r\n",
    "#         self.val = val\r\n",
    "#         self.left = left\r\n",
    "#         self.right = right\r\n",
    "class Solution:\r\n",
    "    def __init__(self):\r\n",
    "        self.s = set()\r\n",
    "        \r\n",
    "    def findTarget(self, root: Optional[TreeNode], k: int) -> bool:\r\n",
    "        # self.nums = []\r\n",
    "        # def dfs(root):\r\n",
    "        #     if not root:return\r\n",
    "        #     dfs(root.left)\r\n",
    "        #     self.nums.append(root.val)\r\n",
    "        #     dfs(root.right)\r\n",
    "        # dfs(root)\r\n",
    "        # i, j = 0, len(self.nums) - 1\r\n",
    "        # while i < j:\r\n",
    "        #     if self.nums[i] + self.nums[j] == k:\r\n",
    "        #         return True\r\n",
    "        #     elif self.nums[i] + self.nums[j] > k:\r\n",
    "        #         j -= 1\r\n",
    "        #     else:\r\n",
    "        #         i += 1\r\n",
    "        # return False\r\n",
    "        if root is None:\r\n",
    "            return False\r\n",
    "        if k - root.val in self.s:\r\n",
    "            return True\r\n",
    "        self.s.add(root.val)\r\n",
    "        return self.findTarget(root.left, k) or self.findTarget(root.right, k)\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTarget(self, root: Optional[TreeNode], k: int) -> bool:\n",
    "        def f(node):\n",
    "            if not node:\n",
    "                return False\n",
    "            if k-node.val in ss:\n",
    "                return True\n",
    "            ss.add(node.val)\n",
    "            return f(node.left) or f(node.right)\n",
    "        ss=set()\n",
    "        return f(root)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\r\n",
    "# class TreeNode:\r\n",
    "#     def __init__(self, val=0, left=None, right=None):\r\n",
    "#         self.val = val\r\n",
    "#         self.left = left\r\n",
    "#         self.right = right\r\n",
    "class Solution:\r\n",
    "    def findTarget(self, root: Optional[TreeNode], k: int) -> bool:\r\n",
    "        s = set()\r\n",
    "        def dfs(root):\r\n",
    "            if not root:\r\n",
    "                return False\r\n",
    "            if k - root.val in s:\r\n",
    "                return True\r\n",
    "            s.add(root.val)\r\n",
    "            return dfs(root.left) or dfs(root.right)\r\n",
    "        return dfs(root)        \r\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.s = set()\n",
    "\n",
    "    def findTarget(self, root: Optional[TreeNode], k: int) -> bool:\n",
    "        if not root:\n",
    "            return False\n",
    "        if k - root.val in self.s:\n",
    "            return True\n",
    "        self.s.add(root.val)\n",
    "        return self.findTarget(root.left, k) or self.findTarget(root.right, k)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.vals = set()\n",
    "\n",
    "    def findTarget(self, root: Optional[TreeNode], k: int) -> bool:\n",
    "        if root==None: return False\n",
    "\n",
    "        if k-root.val in self.vals:\n",
    "            return True\n",
    "        \n",
    "        self.vals.add(root.val)\n",
    "\n",
    "        return self.findTarget(root.left,k) or  self.findTarget(root.right,k) \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTarget(self, root: Optional[TreeNode], k: int) -> bool:\n",
    "        \n",
    "\n",
    "        check = dict()\n",
    "\n",
    "        def DFS(root):\n",
    "            if not root:\n",
    "                return False \n",
    "            x = root.val \n",
    "            if k-x in check:\n",
    "                return True \n",
    "            check[x] = 1\n",
    "\n",
    "            return DFS(root.left) or DFS(root.right)\n",
    "        return DFS(root)\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTarget(self, root: Optional[TreeNode], k: int) -> bool:\n",
    "        self.d = defaultdict(bool)\n",
    "        self.k = k\n",
    "        self.ans = False\n",
    "        self.dfs(root)\n",
    "        return self.ans\n",
    "\n",
    "    def dfs(self, root):\n",
    "        if not root:\n",
    "            return \n",
    "        self.dfs(root.left)\n",
    "        if self.d[root.val]:\n",
    "            self.ans = True\n",
    "            return\n",
    "        self.d[self.k-root.val] = True\n",
    "        self.dfs(root.right)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTarget(self, root: Optional[TreeNode], k: int) -> bool:\n",
    "        self.res = []\n",
    "        self.dfs(root)\n",
    "        maps = {}\n",
    "        for i in range(len(self.res)):\n",
    "            if k - self.res[i] in maps:\n",
    "                return True\n",
    "            maps[self.res[i]] = i\n",
    "        return False\n",
    "    \n",
    "    def dfs(self, root):\n",
    "        if not root:\n",
    "            return\n",
    "        self.dfs(root.left)\n",
    "        self.res.append(root.val)\n",
    "        self.dfs(root.right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTarget(self, root: Optional[TreeNode], k: int) -> bool:\n",
    "        vals = []\n",
    "        \n",
    "        def travel(node):\n",
    "            if not node:\n",
    "                return\n",
    "            \n",
    "            travel(node.left)\n",
    "            vals.append(node.val)\n",
    "            travel(node.right)\n",
    "        \n",
    "        travel(root)\n",
    "\n",
    "        left = 0\n",
    "        right = len(vals) - 1\n",
    "\n",
    "        while left < right:\n",
    "            total = vals[left] + vals[right]\n",
    "            if total == k:\n",
    "                return True\n",
    "            elif total < k:\n",
    "                left += 1\n",
    "            else:\n",
    "                right -= 1\n",
    "\n",
    "        return False\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def findTarget(self, root: Optional[TreeNode], k: int) -> bool:\n",
    "        def bl(r):\n",
    "            if not r:return []\n",
    "            return [r.val]+bl(r.left)+bl(r.right)\n",
    "        l=bl(root)\n",
    "        print(l)\n",
    "        if len(l)==1:return False\n",
    "        while len(l)>1:\n",
    "            i=l.pop()\n",
    "            if i!=None and k-i in l:\n",
    "                return True\n",
    "        return False\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
